class Solution {
    // 计算斜率
    string cal(int x1, int y1, int x2, int y2)
    {
        int dx = abs(x2 - x1);  // 取绝对值方便计算，后面如果是负数再添负号
        int dy = abs(y2 - y1);
        int t = gcd(dx, dy);    // 求它们的最小公约数，时间复杂度是O(logN);
        string ret = to_string(dy / t) + "_" + to_string(dx / t);
        if((x2 < x1 && y2 > y1) || (x2 > x1 && y2 < y1))
            ret = "-" + ret;    // 负数
        return ret;
    }
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        int ret = 0;
        // 枚举每个中心点，看这个中心点和其他任意一点斜率是否一样
        // 时间复杂度O(N^2 * logN)
        // 空间复杂度O(N)   使用了哈希表
        for(int i = 0; i < n; i++)
        {
            int x1 = points[i][0], y1 = points[i][1];   // 中心点
            unordered_map<string, int> hash;            // [斜率，点数]
            int tmp = 0;                                // 以该点为中心点时直线上最多的点数
            // 这里斜率处理为字符串，并且分子分母都除以它们的最小公约数化成最简分子式
            for(int j = i + 1; j < n; j++)
            {
                int x2 = points[j][0], y2 = points[j][1];
                hash[cal(x1, y1, x2, y2)]++;
                tmp = max(tmp, hash[cal(x1, y1, x2, y2)]);
            }
            ret = max(ret, tmp + 1);    // 加一是加上中心点这个点
        }
        return ret;
    }
};